package graph

import "container/list"

func TopologicalSort(graph Graph) []int {
	// 结果数组
	ans := []int{}
	// 记录节点的入度的map
	nodeInMap := map[*Node]int{}
	// 入度为0的节点才可以进入队列
	zeroInQueue := list.New()
	// 遍历图中，点集，并将入度为0的点放入队列
	for _, v := range graph.Nodes {
		nodeInMap[v] = v.In
		if v.In == 0 {
			zeroInQueue.PushBack(v)
		}
	}

	// 入度为0的队列不为空时，结果就没有搜集完毕
	for zeroInQueue.Len() > 0 {
		// 取出入度为0的一个点
		node := zeroInQueue.Remove(zeroInQueue.Front()).(*Node)
		// 加入结果集
		ans = append(ans, node.Val)

		// 消除搜集点的影响，将该点的直接相邻节点的入度减1，如果入度减完后为0，则放入队列
		for _, next := range node.Nexts {
			nodeInMap[next]--
			if nodeInMap[next] == 0 {
				zeroInQueue.PushBack(next)
			}
		}
	}
	return ans
}